// 关键路径
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\6Graph\2_Adjacency_Matrix\Adj_Matrix.h"

int find_path(Adj_Matrix G, int v, int path[])
{
    int lenth = -1;
    int top = -1;
    int stack[MAX];
    int visited[MAX] = {0};
    path[++top] = v;
    int w = -1;
    while (top >= 0)
    {
        int p = path[top];
        visited[p] = 1;
        int n = ++w;
        int flag = 0;
        while (n < G.node_num)
        {
            if (G.M[p][n] == 1 && visited[n] == 0)
            {
                flag = 1;
                path[++top] = n;
                visited[top] = 1;
                w = -1;
                break;
            }
            n++;
        }
        if (!flag) // 找到了出度为0的点
        {
            if (top > lenth)
            {
                lenth = top;
                for (int t = 0; t <= top; t++)
                    stack[t] = path[t];
            }
            w = p;
            visited[top] = 0;
            top--;
        }
    }
    return lenth;
}

void Critical_Path(Adj_Matrix G)
{
    // 1.找到入度为0的节点作为起始点
    int degree[MAX] = {0};
    for (int i = 0; i < G.node_num; i++)
    {
        for (int j = 0; j < G.node_num; j++)
        {
            if (G.M[j][i] != 0 && G.M[j][i] != INFINITY)
            {
                degree[i]++;
            }
        }
    }
    int stack[MAX];
    int top = -1;
    for (int i = 0; i < G.node_num; i++)
    {
        if (!degree[i])
        {
            stack[++top] = i;
        }
    }
    int path[MAX];
    int stack1[MAX];
    int length = -1;
    for (int i = 0; i <= top; i++)
    {
        int l = find_path(G, i, path);
        if (l >= length)
        {
            length = l;
            for (int i = 0; i <= length; i++)
                printf("%3d", path[i]);
            printf("\n");
        }
    }
}

int main()
{
    /*******************code*******************/
    Adj_Matrix G;
    creat_critical(G);
    Critical_Path(G);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
